Article Outline
33. Search in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.</br> (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).</br> You are given a target value to search. If found in the array return its index, otherwise return -1.
class Solution {
public int search(int[] nums, int target) {
int lo = 0;
int hi = nums.length-1;
// find the piviot
// binary search without =
// then lo = mid+1;
while(lo<hi){
int mid = (lo+hi)/2;
if(nums[mid]>nums[hi]){
lo=mid+1;
}else{
hi=mid;
}
}
int piviot = lo;
lo = 0;
hi = nums.length-1;
/*
binary search with =
then lo = mid+1; hi = mid-1
this method pretend to do binary search in unrotated
When it comes to compare, it find the value from
rotated list.
*/
while(lo<=hi){
int mid = (lo+hi)/2;
int realmid = (mid+piviot)%nums.length;
if(nums[realmid]==target) return realmid;
if(nums[realmid]<target) lo = mid+1;
else hi = mid-1;
}
return -1;
}
}